// https://leetcode.cn/problems/clone-graph/description/?envType=study-plan-v2&envId=top-interview-150

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
private:
    unordered_map<Node*, Node*> mp;
    void dfsNode(Node* node) {
        if (mp.count(node)) {
            return;
        }

        Node* clonedNode = new Node(node->val);
        mp[node] = clonedNode;
        for (Node* neighbor : node->neighbors) {
            dfsNode(neighbor);
        }
    }

public:
    Node* cloneGraph(Node* node) {
        if (node == nullptr) {
            return nullptr;
        }

        dfsNode(node);

        for (auto it = mp.begin(); it != mp.end(); it++) {
            Node* originNode = it->first;
            Node* clonedNode = it->second;

            for (Node* neighbor : originNode->neighbors) {
                clonedNode->neighbors.emplace_back(mp[neighbor]);
            }
        }
        return mp[node];
    }
};